package leetcode.medium.pondsize;

import util.annotation.Solved;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/pond-sizes-lcci/">Question Link</a>
 * <b>[Medium] 水域大小</b>
 * @author wangzefeng
 * @since 2023-06-22
 */
@Solved
public class Solution {
    private List<Integer> result = new ArrayList<>();
    private boolean[][] visited;
    private int size = 0;
    public int[] pondSizes(int[][] land) {
        visited = new boolean[land.length][land[0].length];
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                size = 0;
                dfs(i, j, land);
                if (size > 0) {
                    result.add(size);
                }
            }
        }
        result.sort(Integer::compareTo);
        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        return resultArray;
    }

    private void dfs(int i, int j, int[][] land) {
        if (i < 0 || i >= land.length) {
            return;
        }
        if (j < 0 || j >= land[0].length) {
            return;
        }
        if (visited[i][j]) {
            return;
        }
        int value = land[i][j];
        visited[i][j] = true;
        if (value == 0) {
            size++;
            dfs(i - 1, j, land);
            dfs(i + 1, j, land);
            dfs(i, j - 1, land);
            dfs(i, j + 1, land);
            dfs(i - 1, j - 1, land);
            dfs(i + 1, j - 1, land);
            dfs(i - 1, j + 1, land);
            dfs(i + 1, j + 1, land);
        }
    }

    public static void main(String[] args) {
        int[][] land = new int[][] {
                new int[] {0, 2, 1, 0},
                new int[] {0, 1, 0, 1},
                new int[] {1, 1, 0, 1},
                new int[] {0, 1, 0, 1}
        };
        int[] result = new Solution().pondSizes(land);
        System.out.println(Arrays.toString(result));
    }


}
